package LeetCode刷题.之前的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-16 15:26
 * @description: Functions of this class is Trie树应用DNS反向搜索
 **/
public class Trie树应用DNS反向搜索 {
    private static TNode trie=new TNode();
    private static final int Maxnum=11;//只包含0~9还有，所以一共有11个字符
    private static class TNode{
        boolean isLeaf=false;
        String url;
        TNode child[]=new TNode[Maxnum];
    }
    private static int getIndex(char c){
        return c=='.'?10:c-'0';
    }
    private static void insert(String ip,String url){
        int level=ip.length();
        TNode p=trie;
        for(int i=0;i<level;i++){
            //根据层数，来对每一个ip中的每个字符进行拆解
            int index=getIndex(ip.charAt(i));//然后转化为trie树中的索引号
            if(p.child[index]==null){
                //如果该索引下的节点未创建的话，就创建新节点
                p.child[index]=new TNode();
            }
            //如果已经创建了，就往下走
            p=p.child[index];
        }
        //最后出来了循环后，最后那个节点就是叶子
        p.isLeaf=true;
        p.url=url;
    }
    private static String search(String ip){
        int level=ip.length();
        TNode p=trie;
        for(int i=0;i<level;i++){
            int index=getIndex(ip.charAt(i));
            if(p.child[index]==null){
                return null;//说明该字符就不存在
            }
            //要是存在的话，就继续往下走
            p=p.child[index];
        }
        //走出循环后，即所有元素都已经判断完毕了，
        if(p!=null&&p.isLeaf){
            //如果这个时候p不为空，且p现在为叶子结点的话，就说明找到了
            return p.url;
        }
        return null;
    }
    public static void main(String args[]){
        String url[]={"www.baidu.com","www.jd.com","www.taobao.com"};
        String ip[]={"10.112.34.55","192.168.1.199","192.168.36.1"};
        for(int i=0;i<ip.length;i++){
          insert(ip[i],url[i]);
        }
        String s="192.168.36.1";
        System.out.println(search(s));
    }
}